package dp_algorithm.leetcode.medium;

/**
 * @author bruin_du
 * @description 把数字翻译成字符串
 * @date 2022/5/24 16:51
 **/
public class Offer46_TranslateNum {
    public int translateNum(int num) {
        //方法一：在字符串上截取进行动态规划
         translateNum1(num);

        //方法二:直接在数字通过取余和取商得到各位数
        //因为从前往后和从后往前是一样的
        return translateNum2(num);
    }

    private int translateNum2(int num) {
        int a = 1,b = 1,c = 1;
        while(num != 0){
            int x1 = num % 10;
            num /= 10;
            int x2 = num % 10;
            int x = x2 * 10 + x1;
            c = x >= 0 && x <= 25 ? a + b : b;
            a = b;
            b = c;
        }
        return c;
    }

    private int translateNum1(int num) {
        int a = 1,b = 1,c = 1;
        String str = String.valueOf(num);
        for (int i = 2; i <= str.length(); i++) {
            String tmp = str.substring(i - 2,i);
            //dp[i]代表走到当前字符有多少中匹配方案,而且和斐波那契数列很像
            //当str[i-2,i]在[10,25]区间时,满足字符串翻译
            //截取的这两个字符只翻译一个时,有f(i - 1)种方案
            //翻译两个字符时,方案数有f(i- 2)个,加起来就有f(i - 1) + f(i - 2),dp[i] = dp[i - 1] + dp[i - 2]
            //当不在这个区间时,只有翻译一个字符,就只有f(i - 1)种方案,dp[i]=dp[i−1]
            c = tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0 ? a + b : b;
            a = b;
            b = c;
        }
        return c;
    }
}
